import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;

import java.util.Arrays;
import java.util.stream.Stream;

/**
 * 有效的数独
 * 题目：判断一个9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
 * <p>
 * 数字1-9在每一行只能出现一次。
 * 数字1-9在每一列只能出现一次。
 * 数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。
 * <p>
 * 数独部分空格内已填入了数字，空白格用 '.' 表示。
 * <p>
 * 来源：力扣（LeetCode-36）
 * 链接：https://leetcode-cn.com/problems/valid-sudoku
 *
 * @author godfrey
 * @since 2020-11-06
 */
@DisplayName("有效的数独")
public class ValidSudoku extends BaseTest {

    static Stream<Arguments> testArguments() {
        return Stream.of(
                Arguments.arguments((Object) new char[][]{
                        {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                        {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                        {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                        {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                        {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                        {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                        {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                        {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                        {'.', '.', '.', '.', '8', '.', '.', '7', '9'}}),
                Arguments.arguments((Object) new char[][]{
                        {'8', '3', '.', '.', '7', '.', '.', '.', '.'},
                        {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                        {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                        {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                        {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                        {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                        {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                        {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                        {'.', '.', '.', '.', '8', '.', '.', '7', '9'}})
        );
    }

    @DisplayName("时间复杂度O(n^2)，空间复杂度O(1)")
    @ParameterizedTest
    @MethodSource("testArguments")
    void isValidSudoku(char[][] board) {
        boolean[] used = new boolean[9];
        for (int i = 0; i < 9; ++i) {
            Arrays.fill(used, false);
            //检查行
            for (int j = 0; j < 9; ++j) {
                if (!check(board[i][j], used)) {
                    System.out.println(false);
                    return;
                }
            }
            Arrays.fill(used, false);
            //检查列
            for (int j = 0; j < 9; ++j) {
                if (!check(board[j][i], used)) {
                    System.out.println(false);
                    return;
                }
            }
        }
        //检查九个子格子
        for (int r = 0; r < 3; ++r) {
            for (int c = 0; c < 3; ++c) {
                Arrays.fill(used, false);
                for (int i = r * 3; i < r * 3 + 3; ++i) {
                    for (int j = c * 3; j < c * 3 + 3; ++j) {
                        if (!check(board[i][j], used)) {
                            System.out.println(false);
                            return;
                        }
                    }
                }
            }
        }
        System.out.println(true);
    }

    private static boolean check(char ch, boolean[] used) {
        if (ch == '.') {
            return true;
        } else if (used[ch - '1']) {
            return false;
        }
        return used[ch - '1'] = true;
    }
}
